package com.hxm.demo.newcoder;

import java.util.ArrayList;
import java.util.List;

/**
 * description: add a description
 *
 * @author huangxiaoming
 * @version 1.0.0
 * @date 2023/08/23 15:41:52
 */
public class TestBM5 {
    public static void main(String[] args) {
        ArrayList<ListNode> lists = new ArrayList<>();
        ListNode pHead1 = new ListNode(1);
        pHead1.next = new ListNode(3);
        pHead1.next.next = new ListNode(5);
        lists.add(pHead1);

        ListNode pHead2 = new ListNode(1);
        pHead2.next = new ListNode(3);
        pHead2.next.next = new ListNode(5);
        lists.add(pHead2);

        ListNode listNode = mergeKLists2(lists);
        System.out.println(listNode);
    }

    public static ListNode mergeKLists1(ArrayList<ListNode> lists) {
        // write code here
        ListNode pre = null;
        for (int i = 0; i < lists.size(); i++) {
            pre = merge(pre, lists.get(i));
        }
        return pre;
    }


    public static ListNode mergeKLists2(ArrayList<ListNode> lists) {
        // write code here
        return dept(lists, 0, lists.size() - 1);
    }

    private static ListNode dept(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return lists.get(left);
        }
        int mid = (left + right) / 2;
        return merge(dept(lists, 0, mid), dept(lists, mid + 1, right));
    }


    public static ListNode merge(ListNode first, ListNode second) {
        // write code here
        if (first == null) {
            return second;
        }
        if (second == null) {
            return first;
        }
        if (first.val <= second.val) {
            first.next = merge(first.next, second);
            return first;
        } else {
            second.next = merge(first, second.next);
            return second;
        }
    }

}
